package slideWindow;

/**
 * @author pengfei.hpf
 * @date 2020/3/10
 * @verdion 1.0.0
 * 1151. 最少交换次数来组合所有的 1
 * 给出一个二进制数组 data，你需要通过交换位置，将数组中 任何位置 上的 1 组合到一起，并返回所有可能中所需 最少的交换次数。
 *
 *
 *
 * 示例 1：
 *
 * 输入：[1,0,1,0,1]
 * 输出：1
 * 解释：
 * 有三种可能的方法可以把所有的 1 组合在一起：
 * [1,1,1,0,0]，交换 1 次；
 * [0,1,1,1,0]，交换 2 次；
 * [0,0,1,1,1]，交换 1 次。
 * 所以最少的交换次数为 1。
 * 示例 2：
 *
 * 输入：[0,0,0,1,0]
 * 输出：0
 * 解释：
 * 由于数组中只有一个 1，所以不需要交换。
 * 示例 3：
 *
 * 输入：[1,0,1,0,1,0,0,1,1,0,1]
 * 输出：3
 * 解释：
 * 交换 3 次，一种可行的只用 3 次交换的解决方案是 [0,0,0,0,0,1,1,1,1,1,1]。
 *
 *
 * 提示：
 *
 * 1 <= data.length <= 10^5
 * 0 <= data[i] <= 1
 */
public class MinSwaps {
    public int minSwaps(int[] data) {
        if(data == null || data.length == 0){
            return 0;
        }
        int count1 = 0;
        for(int i: data){
            if(i == 1){
                count1++;
            }
        }
        if(count1 == 0){
            return 0;
        }
        int outside1 = count1;
        int inside0 = 0;
        int left = 0;
        int right = 0;
        int min = data.length;
        while(right < data.length){
            int i = data[right];
            if(i != 1){
                inside0 ++;
            } else {
                outside1 --;
            }
            right ++;
            while(left < data.length && inside0 >= outside1){
                if(outside1 == inside0){
                    min = Math.min(min, outside1);
                }
                int l = data[left];
                if(l == 1){
                    outside1 ++;
                } else {
                    inside0 --;
                }
                left ++;
            }
        }
        return min;
    }

    //TODO: 保持一个窗口, 窗口大小和1的总数一样大, 不断滑动, 这里面包含的1最多的那个窗口就是需要交换次数最少的那个
    public int minSwapsII(int[] data) {
        if(data == null || data.length == 0){
            return 0;
        }
        int count1 = 0;
        for(int i: data){
            if(i == 1){
                count1++;
            }
        }
        if(count1 <= 1){
            return 0;
        }
        int min = data.length;
        int left = 0;
        int one = 0;
        for(int i = 0; i < data.length; i ++){
            if(data[i] == 1){
                one ++;
            }
            if(i - left >= count1 - 1){
                min = Math.min(min, count1 - one);
                if(data[left] == 1){
                    one --;
                }
                left ++;
            }
        }
        return min;
    }
}
